package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-09-01 02:22
 */
public class Pro0010 {
    public boolean isMatch(String s, String p) {
        if(s.length() == 0 && p.length() == 0) return true;
        if(p.length() == 0) return false;
        boolean[][] dp = new boolean[s.length()+1][p.length() + 1];
        dp[0][0] = true;
        for(int i=0; i<=s.length(); i++) {
            for(int j=1; j<= p.length(); j++) {
                if(j > 1 && p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-2] || (i>0 &&(s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') && dp[i-1][j]);
                }else {
                    dp[i][j] = i>0 && dp[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.');
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}
